<!DOCTYPE html>
<html lang="zh-CN">

<head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">
    <link rel="shortcut icon" href="">
    <title>Maze and AStar</title>
    <style type="text/css">
        body {
            background-color: #eccc68;
        }

        canvas {
            width: 400px;
            height: 300px;
            border: 1px solid black;
        }
    </style>
</head>

<body>
    <h1>AStar</h1>
    <script type="module">
        import {createCanvas, vector2, animation, mouse, curve, circle, rect, line, fill, stroke, lineWidth, frame, noloop} from './spring/board.js'

        const width = 1200, height = 800, w = 50
        const cols = ~~(width / w), rows = ~~(height / w)
        const openList = [], closeList = [], grid = [], stack = []

        class Spot {
            constructor(i, j, wall = 0.6) {
                this.i = i
                this.j = j
                this.g = 0
                this.h = 0
                this.f = 0
                this.neighbors = []
                this.previous = null
                // this.wall = Math.random() > wall
                this.walls = [true, true, true, true]
            }
            show(color) {
                const { i, j, wall } = this
                rect((i + 0.5) * w, (j + 0.5) * w, w - 1, w - 1)
                // circle((i + 0.5) * w, (j + 0.5) * w, (w - 1) / 2, 20)
                // fill(wall ? '#000' : color)
                for (let i = 0; i < 4; ++i) {
                    if (!this.walls[i]) continue
                    let x = this.i * w, y = this.j * w
                    i === 0 && line(x    , y    , x + w, y) // 0
                    i === 1 && line(x + w, y    , x + w, y + w) // 1
                    i === 2 && line(x    , y + w, x + w, y + w) // 2
                    i === 3 && line(x    , y    , x    , y + w) // 3
                    stroke('#000', 2)
                }

                if (this.visited) {
                    rect((this.i + 0.5) * w + 0.5, (this.j + 0.5) * w + 0.5, w - 1, w - 1)
                    fill('#7bed9f')
                }
            }
            addNeighor(grid) {
                const { i, j, neighbors } = this
                i > 0        && neighbors.push(grid[i - 1][j])
                i < cols - 1 && neighbors.push(grid[i + 1][j])
                j > 0        && neighbors.push(grid[i][j - 1])
                j < rows - 1 && neighbors.push(grid[i][j + 1])
                /*
                i > 0 && j > 0        && neighbors.push(grid[i - 1][j - 1])
                i > 0 && j < rows - 1 && neighbors.push(grid[i - 1][j + 1])
                i < cols - 1 && j > 0 && neighbors.push(grid[i + 1][j - 1])
                i < cols - 1 && j < rows - 1 && neighbors.push(grid[i + 1][j + 1])
                */
            }

            checkNeigbors(grid) {
                const { i, j } = this
                let neigbors = []
                let top    = j > 0 && grid[i][j - 1]
                let right  = i < cols - 1 && grid[i + 1][j]
                let bottom = j < rows - 1 && grid[i][j + 1]
                let left   = i > 0 && grid[i - 1][j]

                if (top && !top.visited) {
                    neigbors.push(top)
                }
                if (right && !right.visited) {
                    neigbors.push(right)
                }
                if (bottom && !bottom.visited) {
                    neigbors.push(bottom)
                }
                if (left && !left.visited) {
                    neigbors.push(left)
                }
                if (neigbors.length > 0) {
                    let r = ~~(Math.random() * neigbors.length)
                    return neigbors[r]
                }
                return undefined
            }

            heightLight() {
                rect((this.i + 0.5) * w, (this.j + 0.5) * w, w, w)
                fill('#ff6348')
            }
        }

        function removeFromArray(array, el) {
            if (array instanceof Array) {
                for (let i = 0; i < array.length; ++i) {
                    if (array[i] === el) {
                        array.splice(i, 1)
                    }
                }
            }
        }

        /**
         * 破墙
         */
        function removeWall(a, b) {
            let x = a.i - b.i
            if (x === 1) {
                a.walls[3] = false
                b.walls[1] = false
            } else if (x === -1) {
                a.walls[1] = false
                b.walls[3] = false
            }

            let y = a.j - b.j
            if (y === 1) {
                a.walls[0] = false
                b.walls[2] = false
            } else if (y === -1) {
                a.walls[2] = false
                b.walls[0] = false
            }
        }

        /**
         * 破墙
         */
        function through(a, b) {
            let x = a.i - b.i
            if (x === 1) {
                return !a.walls[3] && !b.walls[1]
            } else if (x === -1) {
                return !a.walls[1] && !b.walls[3]
            }

            let y = a.j - b.j
            if (y === 1) {
                return !a.walls[0] && !b.walls[2]
            } else if (y === -1) {
                return !a.walls[2] && !b.walls[0]
            }
        }

        function heuristic(current, target) {
            return Math.abs(current.i - target.i) + Math.abs(current.j - target.j)
            // return Math.sqrt(Math.pow(current.i - target.i, 2) + Math.pow(current.j - target.j, 2))
        }

        for (let i = 0; i < cols; ++i) {
            grid[i] = []
            for (let j = 0; j < rows; ++j) {
                grid[i][j] = new Spot(i, j)
            }
        }
        for (let i = 0; i < cols; ++i) {
            for (let j = 0; j < rows; ++j) {
                grid[i][j].addNeighor(grid)
            }
        }
        let start = grid[0][0], end = grid[cols - 1][rows - 1]
        let current = start
        start.wall = false
        end.wall = false
        openList.push(start)
        createCanvas(width / 2, height / 2)
        // 1-启动， 0-停止， -1-no solution, 2-建造
        let running = 2
        function draw() {
            let path = []
            if (running === 2) {
                maze()
            } else {
                astar()
            }

            for (let i = 0; i < cols; ++i) {
                for (let j = 0; j < rows; ++j) {
                    grid[i][j].show()
                }
            }
            for (let item of openList) {
                item.show('rgba(0, 255, 0, .8)')
            }
            for (let item of closeList) {
                item.show('rgba(0, 255, 255, .8)')
            }
            if (running > -1) {
                let temp = current
                while(temp.previous) {
                    path.push(temp)
                    temp = temp.previous
                }
                path.push(start)

                for (let item of path) {
                    item.show('rgba(255, 0, 255, .8)')
                }
                let verties = []
                for (let item of path) {
                    verties.unshift({x: (item.i + .5) * w, y: (item.j + .5) * w})
                }
                lineWidth(5)
                curve(verties, stroke)
            }

        }

        function maze () {
            current.visited = true
            current.heightLight()
            // 选中下一方块
            let next = current.checkNeigbors(grid)
            if (next) {
                // 入栈
                stack.push(current)
                // 连通当前方块与下一方块
                removeWall(current, next)
                // 跳到下一方块
                current = next
            } else if (stack.length > 0) {
                // 出栈
                current = stack.pop()
            }
            if (stack.length <= 0) {
                running = 1
            }
        }

        function astar() {
            if (openList.length > 0 && running > 0) {
                let index = 0
                for (let i = 0; i < openList.length; ++i) {
                    if (openList[i].f < openList[index].f) {
                        index = i
                    }
                }
                current = openList[index]
                removeFromArray(openList, current)
                closeList.push(current)
                if (current === end) {
                    // openList.length = 0
                    running = 0
                    console.log('DONE!')
                    return
                }
                let neighbors = current.neighbors
                for (let i = 0; i < neighbors.length; ++i) {
                    let neighbor =  neighbors[i]
                    // can't run the wall or pass
                    if (!closeList.includes(neighbor) && through(current, neighbor)) {
                        let g = current.g + 1
                        if (openList.includes(neighbor)) {
                            if (g < neighbor.g) {
                                neighbor.g = g
                            } else {
                                // do not run this spot
                                continue
                            }
                        } else {
                            neighbor.g = g
                            openList.push(neighbor)
                        }
                        neighbor.h = heuristic(neighbor, end)
                        neighbor.f = neighbor.g + neighbor.h
                        neighbor.previous = current
                    }
                }
            } else {
                if (running > 0) {
                    console.log("no solution")
                    running = -1
                    noloop()
                }
            }
        }

        animation(draw)
    </script>
</body>

</html>